package com.lun.swordtowardoffer2.c08;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

import com.lun.util.BinaryTree.TreeNode;

public class FindTarget {

	//方法一：利用哈希表，空间复杂度为O(n)的解法
	public boolean findTarget(TreeNode root, int k) {
		Set<Integer> cache = new HashSet<>();
		LinkedList<TreeNode> stack = new LinkedList<>();
		TreeNode cur = root;
		while(!stack.isEmpty() || cur != null) {
			if(cur != null) {
				stack.push(cur);
				cur = cur.left;
			}else {
				cur = stack.pop();
				if(cache.contains(k - cur.val)) {
					return true;
				}
				cache.add(cur.val);
				cur = cur.right;
			}
		}
		return false;
	}
	
	public class BSTIterator {

		private LinkedList<TreeNode> stack;
		private TreeNode cur;
		private boolean left2RightFlag;
		
		public static final boolean LEFT_TO_RIGHT = true;
		public static final boolean RIGHT_TO_LEFT = false;

		public BSTIterator(TreeNode root) {
			this.cur = root;
			this.left2RightFlag = LEFT_TO_RIGHT;
			stack = new LinkedList<>();
		}
		
		public BSTIterator(TreeNode root, boolean left2RightFlag) {
			this(root);
			this.left2RightFlag = left2RightFlag;
		}

		public int next() {
			while(cur != null) {
				stack.push(cur);
				cur = left2RightFlag ? cur.left : cur.right;
			}
			cur = stack.pop();
			int val = cur.val;
			cur = left2RightFlag ? cur.right : cur.left;
			return val;
		}
		
		public boolean hasNext() {
			return !stack.isEmpty() || cur != null;
		}
	}
	
	//方法二：应用双指针，空间复杂度为O(h)的解法
	public boolean findTarget2(TreeNode root, int k) {
		if (root == null)
			return false;
		BSTIterator leftIterator = new BSTIterator(root, BSTIterator.LEFT_TO_RIGHT);
		BSTIterator rightIterator = new BSTIterator(root, BSTIterator.RIGHT_TO_LEFT);
		
		int left = leftIterator.next();
		int right = rightIterator.next();
		
		while(left != right) {
			int sum = left + right;
			if(sum < k) {
				left = leftIterator.next();
			}else if(sum > k){
				right = rightIterator.next();
			}else {
				return true;
			}
		}
		
		return false;
	}
	
	//方法三：中序迭代遍历+二分查找
	public boolean findTarget3(TreeNode root, int k) {
		LinkedList<TreeNode> stack = new LinkedList<>();
		TreeNode cur = root;
		while(!stack.isEmpty() || cur != null) {
			if(cur != null) {
				stack.push(cur);
				cur = cur.left;
			}else {
				cur = stack.pop();
				
				int diff = k - cur.val;
				if(diff != cur.val && find(root, diff)) {
					return true;
				}
				
				cur = cur.right;
			}
		}
		return false;
	}
	
	private boolean find(TreeNode root, int val) {
		TreeNode cur = root;
		
		while(cur != null) {
			if(val < cur.val) {
				cur = cur.left;
			}else if(cur.val < val) {
				cur = cur.right;
			}else {
				return true;
			}
		}
		return false;
	}
	
}
